// 基础类
// 二叉搜索树（BST）是二叉树的一种，但是它只允许你在左侧节点存储（比父节点）小的值，
// 在右侧节点存储（比父节点）大（或者等于）的值。
function BinarySearchTree() {
  var Node = function (key) {
    this.key = key
    this.left = null
    this.right = null
  }
  var insertNode = function (root, newNode) {
    if (root.key > newNode.key) {
      if (root.left) {
        insertNode(root.left, newNode)
      } else {
        root.left = newNode
      }
    } else {
      if (root.right) {
        insertNode(root.right, newNode)
      } else {
        root.right = newNode
      }
    }
  }
  var inOrderTraverseNode = function (node, callback) {
    if (node !== null) {
      inOrderTraverseNode(node.left, callback);
      callback(node.key);
      inOrderTraverseNode(node.right, callback);
    }
  }
  var preOrderTraverseNode = function (node, callback) {
    if (node !== null) {
      callback(node.key);
      preOrderTraverseNode(node.left, callback);
      preOrderTraverseNode(node.right, callback);
    }
  }
  var postOrderTraverseNode = function (node, callback) {
    if (node !== null) {
      postOrderTraverseNode(node.left, callback); //{1} 
      postOrderTraverseNode(node.right, callback); //{2} 
      callback(node.key); //{3} 
    }
  };
  var minNode = function (node) {
    if (node) {
      while (node && node.left) {
        node = node.left
      }
      return node.key
    }
    return null
  }
  var maxNode = function (node) {
    if (node) {
      while (node && node.right !== null) { //{5} 
        node = node.right;
      }
      return node.key;
    }
    return null;
  };
  var findMinNode = function (node) {
    while (node && node.left) {
      node = node.left
    }
    return node
  }
  var searchNode = function (node, key) {
    if (node === null) {
      return false
    }
    if (node.key == key) {
      return true
    } else if (node.key > key) {
      return searchNode(node.left, key)
    } else {
      return searchNode(node.right, key)
    }
  }
  var removeNode = function (node, key) {
    if (node === null) { //{2} 
      return null;
    }
    if (key < node.key) { //{3} 
      node.left = removeNode(node.left, key); //{4} 
      return node; //{5} 
    } else if (key > node.key) { //{6} 
      node.right = removeNode(node.right, key); //{7} 
      return node; //{8} 
    } else { //键等于node.key 
      //第一种情况——一个叶节点
      if (node.left === null && node.right === null) { //{9} 
        node = null; //{10} 
        return node; //{11} 
      }
      //第二种情况——一个只有一个子节点的节点
      if (node.left === null) { //{12} 
        node = node.right; //{13} 
        return node; //{14} 
      } else if (node.right === null) { //{15} 
        node = node.left; //{16} 
        return node; //{17} 
      }
      //第三种情况——一个有两个子节点的节点
      var aux = findMinNode(node.right); //{18} 
      node.key = aux.key; //{19} 
      node.right = removeNode(node.right, aux.key); //{20} 
      return node; //{21} 
    }
  };
  var root = null
  // 插入一个键
  this.insert = function (key) {
    let newNode = new Node(key)
    if (root) {
      insertNode(root, newNode)
    } else {
      root = newNode
    }
  }
  this.inOrderTraverse = function (callback) {
    inOrderTraverseNode(root, callback); //{1} 
  };
  this.preOrderTraverse = function (callback) {
    preOrderTraverseNode(root, callback);
  };
  this.postOrderTraverse = function (callback) {
    postOrderTraverseNode(root, callback);
  };
  this.remove = function (key) {
    root = removeNode(root, key); //{1} 
  };
  this.min = function () {
    return minNode(root); //{1} 
  };
  this.max = function () {
    return maxNode(root);
  };
  this.search = function (key) {
    return searchNode(root, key); //{1} 
  };
  this.getTree = function () {
    return root
  }
}

// insert(key)：向树中插入一个新的键。
// search(key)：在树中查找一个键，如果节点存在，则返回true；如果不存在，则返回false。
// inOrderTraverse：通过中序遍历方式遍历所有节点。
// preOrderTraverse：通过先序遍历方式遍历所有节点。
// postOrderTraverse：通过后序遍历方式遍历所有节点。
//  min：返回树中最小的值/键。
//  max：返回树中最大的值/键。
//  remove(key)：从树中移除某个键。


var tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);

console.log(tree)

// 中序遍历  
// 中序遍历是一种以上行顺序访问BST所有节点的遍历方式，也就是以从最小到最大的顺序访
// 问所有节点。中序遍历的一种应用就是对树进行排序操作。我们来看它的实现：
// tree.inOrderTraverse((key) => {
//   console.log(key)
// })

// 先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构
// 化的文档。
// tree.preOrderTraverse((key) => {
//   console.log(key)
// })

// 后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目
// 录和它的子目录中所有文件所占空间的大小
// tree.postOrderTraverse((key) => {
//   console.log(key)
// })